package graph;

import org.junit.Test;

import java.util.*;

/*
 *@description 最小基因变化
 *@author hkfan
 *@version 1.0
 *@create 2025/6/23 14:14
 */
public class LeetCode_433 {
    //1. 定义node
    class Node{
        String val;
        List<Node> nexts;
        int visited;

        public Node(String val) {
            this.val = val;
            this.visited = 0;
            this.nexts = new ArrayList<>();
        }
    }

    @Test
    public void test(){
        System.out.println(minMutation("AACCGGTT","AAACGGTA",new String[]{"AACCGGTA","AACCGCTA","AAACGGTA"}));
    }

    public int minMutation(String startGene, String endGene, String[] bank) {
        //2. 定义
        Map<String,Node> map = new HashMap<>();
        //3. Node加入map
        map.put(startGene,new Node(startGene));
        for (String s : bank) {
            map.put(s,map.getOrDefault(s,new Node(s)));
        }
        //4. 特殊情况返回
        if (startGene.equals(endGene)){
            return 0;
        }
        if (!map.containsKey(endGene)){
            return -1;
        }
        //5. 修改node的nexts
        for (Node node : map.values()) {
            if (!node.val.equals(startGene) && check(startGene,node.val)){
                node.nexts.add(map.get(startGene));
            }
            for (String str : bank) {
                if (!node.val.equals(str) && check(str,node.val)){
                    node.nexts.add(map.get(str));
                }
            }
        }
        //6. 广度优先搜索
        return search(map,startGene,endGene);

    }

    private int search(Map<String, Node> map, String startGene, String endGene) {
        //1. 定义
        int res = 0;
        Queue<Node> queue = new LinkedList<>();
        //2. 循环
        queue.add(map.get(startGene));
        queue.add(null);
        while (!queue.isEmpty()){
            Node node = queue.poll();
            if (node==null){
                res++;
                continue;
            }
            node.visited=1;
            if (node.val.equals(endGene)){
                return res;
            }
            for (Node next : node.nexts) {
                if (next.visited==0){
                    queue.add(next);
                }
            }
            if (queue.peek()==null){
                queue.add(null);
            }
        }
        return -1;
    }

    private boolean check(String str1, String str2) {
        int size = 0;
        for (int i = 0; i < str1.length(); i++) {
            if (str1.charAt(i)!=str2.charAt(i)){
                size++;
            }
        }
        return size==1;
    }
}
